\section{Kryptosysteme basierend auf Elliptischen Kurven}
Elliptic Curve Cryptosystems (ECC) sind das neuste von drei Verfahren, die in der Praxis als relevant für Public Key-Algorithmen etabliert haben. ECC gibt es seit den 1980ern.\\
\\
ECC bietet die gleiche Sicherheit wie RSA oder DL-basierte Systeme in $(\Z/p\Z)$, jedoch mit kürzeren Operanden; 160-256 Bit statt 1024-3072 Bit. Es basiert auf dem verallgemeinerten DL-Problem und kann z.B. auch beim Diffie-Hellman-Verfahren verwendet werden. ECC bietet Verbesserungen in Performance durch weniger Berechnungen und in der Bandbreite durch kürzere Signaturen und Schlüssel. Jedoch ist RSA mit kurzen Public Keys immer noch schneller. Die Mathematik hinter ECC ist erheblich komplizierter im Vergleich zu RSA oder ElGamal.

\subsection{Rechnen mit Elliptischen Kurven}
Als kurze Einführung in das mathematische Konzept werden elliptische Kurven unabhängig von ihrer kryptographischen Anwendung betrachtet. Als erstes wird eine zyklische Gruppe gefunden, die für das Kryptosystem verwendet wird. Die alleinige Existenz ist aber nicht ausreichend; das DL-Problem in der Gruppe muss ausreichend schwer zu berechnen sein.\\
\\
Als erstes werden Polynome verwendet. In diesem Zusammenhang sind damit Funktionen aus reellen Zahlen mit Summen aus Exponenten von $x$ und $y$ gemeint. Diese kann man dadurch abbilden, in dem man alle Wertepaaren $(x,y)$ als Punkt interpretiert. Gleichung (\ref{eq:1}) stellt einen \textbf{Kreis} dar (Abb. \ref{ab:1}). Hier wird das Konzept einer Kurve in $\mathbb{R}$ erklärt und veranschaulicht. Die Kurve ist die Menge aller Paare $(x,y)$ $\in \mathbb{R}^2$, die die Gleichung (hier: $x^2+y^2=r^2$) lösen.\\

\begin{equation}
	 \sqrt{x^2 + y^2} = r	 
	 \label{eq:1}
\end{equation}
 
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_1.jpg}
		\label{ab:1}
	\end{center}
	\caption{Plot von allen Punkten $(x,y)$, für die die Gleichung (\ref{eq:1}) gilt. Dabei ist $r$ die Länge des Vektors.}
\end{figure}

Gleichung (\ref{eq:2}) stellt eine Verallgemeinerung von Gleichung (\ref{eq:1}) dar, nämlich eine \textbf{Ellipse} (Abb. \ref{ab:2}).

\begin{equation}
	\frac{x^2}{a} + \frac{y^2}{b} = 1
	\label{eq:2}
\end{equation}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_2.jpg}
		\label{ab:2}
	\end{center}
	\caption{Plot von allen Punkten $(x,y)$, für die die Gleichung (\ref{eq:2}) gilt. Dabei ist $a$ die Höhe und $b$ die Breite der Ellipse.}
\end{figure}

\pagebreak
\subsubsection{Definition von Elliptischen Kurven}
Durch die beiden Beispiele wird geschlussfolgert, dass wir gewisse Kurven aus Polynomgleichungen erhalten. Kurven sind dabei die Wertepaare $(x,y)$, die die Gleichung lösen. Beispielsweise löst der Punkt $(x = r, y = 0)$ die Kreisgleichung (\ref{eq:1}), der Punkt $(x = r/2, y = r/2$) nicht, da $(\frac{r}{2})^2+(\frac{r}{2})^2 = \frac{r^2}{2} \neq r^2$\\
\\
Eine \textbf{elliptische Kurve} ist ein Sonderfall von Polynomgleichung. Für den Gebrauch in der Kryptographie werden die Punkte nicht in den reellen Zahlen, sondern in endlichen Körpern betrachtet; der populärste Fall ist $GF(p)$, in dem jede Arithmetik modulo der Primzahl $p$ gerechnet wird.\\
\\
Für eine Primzahl $p>3$ und $a,b \in \Z_p$ ist eine elliptische Kurve definiert als die Menge aller Paare $(x,y)$ in $\mathbb{Z}_p$, welche
\begin{equation}
	y^2 \equiv x^3 + a \cdot x + b \mod p
\end{equation}
erfüllen, zusammen mit einem imaginären Punkt $\mathcal{O}$ (\textit{point at infinity}), für den gilt
\begin{eqnarray}
	4 \cdot a^3 + 27 \cdot b^2 \not\equiv 0 \mod p
\end{eqnarray}

Die Definition der elliptischen Kurven schließt Spezialfälle (mit sog. Singularitäten) aus, was geometrisch ausgedrückt bedeutet, dass sie keine Schnittpunkte mit sich selbst oder Spitzen hat. Das wird dadurch erreicht, dass die Diskriminante der Kurve nicht Null ist:
\begin{equation*}
  -16(4a^3 + 27b^2) \neq 0
\end{equation*}
\\
Abb. \ref{ab:3} zeigt die beschrieben Funktion (\ref{eq:3}) als Plot. Elliptische Kurven sind keine Ellipsen. Sie sind symmetrisch zur $x$-Achse, da es für jedes $x_i$ zwei Lösungen für $y_i$ gibt:

\begin{eqnarray}
	y_i = \sqrt{x_i^3 + a \cdot x_i + b} \nonumber \\
	y_i ' = -\sqrt{x_i^3 + a \cdot x_i + b} \nonumber
\end{eqnarray}

Außerdem gibt es einen Schnittpunkt mit der $x$-Achse, was daher kommt, dass es sich bei $x^3+ax+b$ um ein kubisches Polynom handelt, das mindestens eine reelle Nullstelle besitzt. Es gibt auch elliptische Kurven mit drei $x$-Achsen-Schnittpunkten, z.B.:

\begin{equation}
	y^2 = x^3 - 3x + 3
	\label{eq:3}
\end{equation}
mit $x_1 \approx -2.1$, $x_{2/3} \approx 1.05 \pm 0.56i$.\\
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_3.jpg}
		\label{ab:2a}
	\end{center}
	\caption{Gleichung (\ref{eq:3}) als Plot in $\mathbb{R}$.}
	\label{ab:3}
\end{figure}

Der erste Schritt ein DL-Problem zu konstruieren ist hiermit getan. Als nächstes muss eine Gruppenoperation für die Punkte gefunden werden.


\subsubsection{Gruppenoperationen von Elliptischen Kurven}
Als erstes wird das Symbol der Gruppenoperation festgelegt: $+$. Die Auswahl ist willkürlich, man hätte genauso gut $\cdot$ nehmen können. \textit{Addition} bedeutet in diesem Fall, dass man aus den Koordinaten der Punkte $P = (x_1,y_1)$ und $Q = (x_2,y_2)$ auf der Kurve die Koordinaten des Punktes $R = (x_3,y_3)$ berechnen kann, der ebenfalls auf der Kurve liegt.

\begin{eqnarray}
	P + Q = R \nonumber \\
	(x_1,y_1) + (x_2,y_2) = (x_3,y_3) \nonumber
\end{eqnarray}

Berücksichtigt man die Darstellung in den reellen Zahlen gibt es eine nette geometrische Interpretation der Addition. Dabei gibt es zwei Fälle:

\begin{enumerate}
	\item Addition verschiedener Punkte (\textit{point addition})
	\item Addition eines Punktes zu sich selbst (\textit{point doubling})
\end{enumerate}

\paragraph{Punktaddition P + Q}
Man zieht eine Gerade durch $P$ und $Q$ und erhält einen Schnittpunkt zwischen der Gerade und der elliptischen Kurve. Dieser Punkt wird an der $x$-Achse gespiegelt und definiert somit den Punkt $R$. %\ref{ab:4}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_4.jpg}
		\label{ab:4}
	\end{center}
	\caption{Geometrische Darstellung von $P + Q = R$.}
\end{figure}

\paragraph{Punktverdopplung P + P}
Für $P + P = R$ kann man auch $2P = R$ schreiben. Die hier verwendete Konstruktion ist etwas anders; man zieht eine Tangente durch $P$ und bekommt als zweiten Punkt den Schnittpunkt zwischen der Tangente und der elliptischen Kurve. $R$ ist dann der Schnittpunkt an der $x$-Achse gespiegelt. %\ref{ab:5}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_5.jpg}
		\label{ab:5}
	\end{center}
	\caption{Geometrische Darstellung von $P + P = R$.}
\end{figure}

Addiert man die Punkte auf diese Weise, werden die meisten notwendigen Bedingungen für Gruppen erfüllt: Assoziativität, Kommutativität, Existenz von neutralem und inversem Element. Die beschriebenen Operationen können auch analytisch ausgedrückt werden und gelten nicht nur in den reellen Zahlen, sondern in jedem Körper. In $GF(p)$ gilt folgende Formel für die Gruppenoperation.

\begin{eqnarray*}
	x_3 = s^2 - x_1 - x_2 \mod p \nonumber \\
	y_3 = s(x_1 - x_3) - y_1 \mod p \nonumber \\
\end{eqnarray*}

mit

\begin{equation*}
	s = \left \{ 
		\begin{array}{rl} 
		\mbox{$\frac{y_2 - y_1}{x_2 - x_1} \mod p$}  &;\mbox{$P \neq Q$}\\
		\mbox{$\frac{3x_1^2 + a}{2y_1} \mod p$}  &;\mbox{$P = Q$}\\
		\end{array} \right.	
\end{equation*}

In Abbildung (\ref{ab:5a}) ist der Sonderfall beschrieben, wenn die Tangente durch den Punkt $P$ parallel zur $x$-Achse ist. Der Schnittpunkt mit der Elliptischen Kurve $E$ in $Q$ ist gleichzeitig der Punkt $Q = - 2P$. Daraus folgt in Gleichung (\ref{eq:3a}), dass die Addition von $P$ und $Q$ das Ergebnis $-P$ ergibt.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=8cm]{ex5_elliptische_kurven/Grafiken/krypto_5a.JPG}
		\label{ab:5a}
	\end{center}
	\caption{Sonderfall: $P + Q$, mit $Q = -2P$.}
\end{figure}

\begin{equation}
 P + Q = P - 2P = -P
 \label{eq:3a}
\end{equation}

\paragraph{Neutrales Element}
Der Parameter $s$ ist die Steigung der Geraden durch $P$ und $Q$ bzw. der Tangenten durch $P$. Was jetzt noch fehlt, ist das neutrale Element $\mathcal{O}$, mit

\begin{equation*}
	P + \mathcal{O} = P
\end{equation*}

für alle Punkte $P$ auf der elliptischen Kurve. Einen solchen Punkt gibt es nicht, weshalb er \textbf{definiert} wird.\\

\paragraph{Inverses Element}
Übereinstimmend mit der Definition einer Gruppe kann man das Inverse $-P$ für alle Gruppenelemente $P$ festlegen:

\begin{equation*}
	P + (-P) = \mathcal{O}
\end{equation*}

Um $-P$ zu finden, muss man nur das Vorzeichen der $y$-Koordinate tauschen;
\begin{eqnarray*}
	P = (x_p,y_p) \nonumber \\
	-P = (x_p,-y_p) \nonumber 
\end{eqnarray*}

Bezogen auf $GF(p)$ ist das einfach zu erreichen, da
\begin{eqnarray*}
	-y_p \equiv p - y_p \mod p \nonumber \\
	-P = (x_p,p-y_p) \nonumber
\end{eqnarray*}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=6cm]{ex5_elliptische_kurven/Grafiken/krypto_6.jpg}
		\label{ab:6}
	\end{center}
	\caption{Geometrische Darstellung von $P$ und $-P$.}
\end{figure}

Man kann zeigen, dass eine elliptische Kurve mit der so definierten Verknüpfung von zwei Punkten die Axiome einer Gruppe erfüllt.

\paragraph{Beispiel}
Wir nehmen $(\mathbb{Z}/17\mathbb{Z})$ mit $E: y^2  \equiv x^3 + 2x + 2 \mod 17$. Darin soll der Punkt $P = (5,1)$ verdoppelt werden.

\begin{eqnarray*}
	2P = P + P = (5,1) + (5,1) = (x_3,y_3) \nonumber \\
	s = \frac{3x_1^2 + a}{2y_1} = (2 \cdot 1)^{-1} (3 \cdot 5^2 + 2) = 2^{-1} \cdot 9 \equiv 9 \cdot 9 \equiv 13 \mod 17 	\nonumber \\
	x_3 = s^2 - x_1 - x_2 = 13^2 - 5 - 5 = 159 \equiv 6 \mod 17 \nonumber \\
	y_3 = s(x_1 - x_3) - y_1 = 13(5 - 6) - 1 = -14 \equiv 3 \mod 17 \nonumber \\
	2P = (5,1) + (5,1) = (6,3)
\end{eqnarray*}



\subsection{Erzeugen eines DL-Problems mit elliptischen Kurven}
Bis zum jetzigen Zeitpunkt haben wir Gruppenoperationen eingeführt (Punktaddition und -verdopplung), ein neutrales Element bereitgestellt und gezeigt wie man das Inverse jedes Punktes auf einer elliptischen Kurve berechnet. Daher haben wir alle Vorraussetzungen erreicht, um das folgende Theorem aufzustellen:

\paragraph{Theorem}
Die Gruppe der Punkte auf einer elliptischen Kurve zusammen mit dem neutralen Element $\mathcal{O}$ hat Untergruppen.
Unter bestimmten Umständen bilden alle Punkte auf einer elliptischen Kurve eine zyklische Gruppe.\\

Nachfolgend ein Beispiel für eine zyklische Gruppe auf einer elliptischen Kurve:

\paragraph{Beispiel}
Ziel ist es, alle Punkte auf der Kurve:

\begin{eqnarray*}
	E: y^2 \equiv x^3 + 2x + 2 \mod 17
\end{eqnarray*}

zu bestimmen, welche gleichzeitig eine zyklische Gruppe bilden. Die Ordnung der Gruppe ist $|E| = 19$, da es 18 Paare ($x,y$) gibt, die $y^2 \equiv x^3 + 2x + 2 \mod 17$ erfüllen (das 19te Element ist $\mathcal{O}$). Im vorliegenden Fall ist die Ordnung der Gruppe eine Primzahl, entsprechend sind auch alle Elemente (außer $\mathcal{O}$) primitiv. Denn allgemein gilt: Die Ordnungen jedes Elements (außer $\mathcal{O}$) sind gleich der Gruppenordnung, da sie diese teilen. \\

Zur Lösung der Aufgabe starten wir mit dem primitiven Element $P = (5,1)$ und berechnen $P$, $2P$, ..., $(|E|)P$. \\
Dies ergibt folgende Elemente:

\begin{align*}
	2P &= (5,1) + (5,1) = (6,3) &&11P = (13,10) & \\
	3P &= 2P + P = (10, 6) &&12P = (0,11) &	\\
	4P &= (3,1) &&13P = (16,4) &	\\
	5P &= (9,16) &&14P = (9,1) &	\\
	6P &= (16,13) &&15P = (3,16) &	\\
	7P &= (0,6) &&16P = (10,11) &	\\
	8P &= (13,7) &&17P = (6,14) &	\\
	9P &= (7,6) &&18P = (5,16) &	\\
	10P &= (7,11) &&19P = \mathcal{O}  & \\
\end{align*}	
	
Die weiteren Elemente spiegeln die zyklische Struktur deutlich wieder:
	
\begin{align*}	
	20P &= 19P + P = \mathcal{O} + P = P \\
	21P &= 2P \\
	&\vdots
\end{align*}

Des Weiteren ist zu erkennen, dass gilt

\begin{eqnarray*}	
	18P + P = \mathcal{O}  \nonumber \\
\end{eqnarray*}

Dies bedeutet $P = (5,1)$ ist das Inverse von $18P = (5,16)$ und umgekehrt.

%Zur Überprüfung werden einfach die x-	und y-Koordinaten verglichen:
%
%\begin{align*}	
%	x: \hspace{1cm} &x_1 = x_2 = 5 &\\
%	y: \hspace{1cm} &-1 \equiv 16 \mod 17 &
%\end{align*}

\paragraph{Hasse-Theorem}
Die Summe aller Punkte einer elliptischen Kurve E modulo p, ist definiert durch die Ordnung $|E|$ und wird eingegrenzt durch:

\begin{eqnarray*}	
 p + 1 - 2 \sqrt{p} \leq |E| \leq p + 1 + 2 \sqrt{p}
\end{eqnarray*}

Das bedeutet die Anzahl aller Punkte auf einer elliptischen Kurve liegt ungefähr in der Größenordnung von $p$. Für eine Kurve mit $2^{160}$ Elementen würden wir eine Primzahl mit der Bitlänge 160 benötigen.

\paragraph{Elliptic Curved Discrete Logarithm Problem (ECDLP)}
Eine elliptische Kurve $E$ ist gegeben und wir betrachten ein primitives Element $P$ und ein anderes Element $T$. Nun besteht das DL-Problem darin, eine natürliche Zahl $d$, mit $1 \leq d \leq |E|$, zu finden damit gilt:

\begin{eqnarray*}	
	\underbrace{P + P + \cdots + P}_{d-\text{mal}} = d P = T
\end{eqnarray*}

In einem Kryptosystem wäre $d$ der Private Key (\textit{Integer}) und $T$ der Public Key, welcher ein Punkt auf der Kurve mit den Koordinaten $T = (x_T,y_T)$ ist. Die Gleichung $d P = T$ wird auch als \textit{Punktmultiplikation} bezeichnet und ist nur eine andere Notation für das d-fache Addieren eines Punktes mit sich selbst.

\paragraph{Beispiel}
Wir führen eine Punktmultiplikation auf die Kurve $y^2 \equiv x^3 + 2x + 2 \mod 17$ durch und berechnen 

\begin{eqnarray*}	
	13P = P + P + \cdots + P
\end{eqnarray*}

mit $P = (5,1)$. Das Ergebnis ist, wie im vorherigen Beispiel, 

\begin{eqnarray*}	
	13P = (16,4)
\end{eqnarray*}

\paragraph{ElGamal} Das ElGamal-Verfahren lässt sich mit elliptischen Kurven realisieren, zum Vergleich:

\begin{align*}
&\text{\textbf{ECC}} & \text{\textbf{ElGamal in}}\ (\Z/p\Z)^* \\
&E: \text{Elliptische Kurve mit Parameter}\ a, b\ \text{und}\ p & p \\
&P: \text{"`Basis"'} & g \\
&d: \text{geheimer Faktor, entspricht Exponent} & a\\
&T = dP: \text{Teil des PublicKey (E,P,T)} & A = g^a\ (p,g,A) \\
&k & b \\
&K = kP & B = g^b \\
&kT & A^b \\
&m & m \\
&kT + m & A^b m\\
&K & B\\
&+: Gruppenoperation & *\\
&\mathcal{O} & 1 \\
\end{align*}

\paragraph{Double-and-Add-Algorithmus für die Punktmultiplikation}
Die Punktmultiplikation ist analog der Potenzierung in multiplikativen Gruppen, d.h. zur effizienten Berechnung kann der square-and multiply-Algorithmus direkt angepasst werden. Es erfolgt lediglich ein Austausch der Operationen: Quadrierung wird zu Verdopplung und Multiplikation zu Addition von $P$. Der endgültige Algorithmus sieht wie folgt aus:

\begin{align*}
&\text{Eingabe:} && \text{Elliptische Kurve E zusammen mit einem Kurvenpunkt}\ P & \\
& 				 &&\text{Der Skalar}\ d = \sum\limits_{i=0}^t d_i 2^i\ \text{mit}\ d_i \in 0, 1\ \text{und}\ d_t = 1 & \\
&\text{Ausgabe:} && T = dP & \\
&\text{Initialisierung:} && T = P & \\
&\text{Algorithmus:} && 1.\hspace{0,5cm} \text{FOR}\ i = t - 1\ \text{DOWNTO}\ 0 & \\
& 											&& 1.1\hspace{1cm} T = T + T \mod n  & \\
& 											&& \hspace{1,5cm}\text{IF}\ d_i = 1 & \\
& 											&& 1.2\hspace{1,5cm} T = T + P \mod n & \\
& 											&& 2. \hspace{0,5cm}\text{RETURN}\ (T) & 
\end{align*}


\textbf{Bem:} Der Algorithmus ist in diesem Fall so organisiert, dass der "`Exponent"' $d$ von links nach rechts abgearbeitet wird. Beim Buchmann erfolgt eine Abarbeitung von rechts nach links, was genauso möglich ist. Mit jedem Schritt erfolgt eine Verdopplung und nur wenn das aktuelle Bit den Wert 1 hat, wird $P$ addiert. 

\paragraph{Beispiel}
Wir betrachten die skalare Multiplikation $26P$ mit der Binärdarstellung:

\begin{eqnarray*}	
	26P = (11010_2) P = (d_4 d_3 d_2 d_1 d_0)_2 P.
\end{eqnarray*}

Der Algorithmus startet mit dem Bit $d_4$ auf der linken und endet mit $d_0$ auf der rechten Seite.
Als konkretes Beispiel wurde $P = (5,1)$ gewählt:

\begin{align*}
&Step:  &&  & \\
&0	&&	P = 1_2 P = (5,1) & \text{Initialisierung, Verarbeitung:}\ d_4 = 1 \\
\\
&1a && P + P = 2P = \textbf{10}_2 P = (6,3) & \text{Verdopplung, Verarbeitung:}\ d_3 \\
&1b && 2P + P = 3P = 10_2 P + 1_2 P = \textbf{11}_2 P = (10,6) & \text{Addition, da}\ d_3 = 1 \\
\\
&2a && 3P + 3P = 6P = 2 (11_2 P) = \textbf{110}_2 P= (16,13)& \text{Verdopplung, Verarbeitung:}\ d_2 \\
&2b &&  & \text{keine Addition, da}\ d_2 = 0 \\
\\
&3a && 6P + 6P = 12P = 2 (110_2 P) = \textbf{1100}_2 P = (0,11)& \text{Verdopplung, Verarbeitung:}\ d_1 \\
&3b && 12P + P = 13P = 1100_2 P + 1_2 P = \textbf{1101}_2 P = (16,4)& \text{Addition, da}\ d_1 = 1 \\
\\
&4a && 13P + 13P = 26P = 2 (1101_2 P) = \textbf{11010}_2  P = (0,6)& \text{Verdopplung, Verarbeitung:}\ d_0 \\
&4b &&  & \text{keine Addition, da}\ d_0 = 0 \\
\end{align*}

Zusammenfassend ist zu sagen, dass eine Verdopplung zu einem Linksshift des Skalars führt, inklusive der Anhängung einer $0$ an die rechte Position.
Bei der Addition mit $P$ wird eine $1$ an die rechte Position angehängt.

An dieser Stelle bietet sich eine geometrische Interpretation des ECDLP an:\\
Es ist eine Startpunkt $P$ gegeben und wir berechnen $2P, 3P, \cdots, dP = T$, d.h. wir springen vor und zurück auf der elliptischen Kurve. Jetzt können wir den Startpunkt $P$ (zugänglicher Parameter) und den Endpunkt $T$ (Public Key) veröffentlichen. Ein Angreifer muss nun herausfinden wie oft wir auf der elliptischen Kurve herumgesprungen sind, um das Kryptosystem zu brechen. Die Anzahl der Sprünge ist der Private Key $d$.